﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace PitOfDespair.Dungeon
{
    /// <summary>
    /// http://www.emanueleferonato.com/2008/12/06/perfect-maze-generation-tile-based-version/
    /// </summary>
    class PerfectMaze : IGenerationStrategy
    {
        /// <summary>
        /// max number of horizontal walkable tiles
        /// </summary>
        private readonly int width;
        /// <summary>
        /// max number of vertical walkable tiles
        /// </summary>
        private readonly int height;
        readonly Random rnd;
        public PerfectMaze(Random rnd, int width, int height)
        {
            this.width = width;
            this.height = height;
            this.rnd = rnd;
        }
        #region IGenerationStrategy Members
        public Tuple<Location[,],int,int> Generate()
        {
            var x = rnd.Next(this.width);
            var y = rnd.Next(this.height);

            return Tuple.Create(Generate(x,y),x,y);
        }

        public Location[,] Generate(int startX, int startY)
        {

            var maze = FromDirectTranslation(this.width, this.height,startX,startY);
            return maze;
        }

        #endregion

        Location[,] FromDirectTranslation(int width, int height, int startX, int startY)
        {
            var original = originalTranslation(width, height, startX, startY);
            var result = new Location[original.GetUpperBound(0) / 2, original.GetUpperBound(1) / 2];
            for (int x = 1; x <= original.GetUpperBound(0); x += 2)
            {
                for (int y = 1; y <= original.GetUpperBound(1); y += 2)
                {
                    var treasure = false;
                    char? current = original[x, y];
                    Func<char, WallType> getWallType = c =>
                        {
                            if (current == PerfectMaze.treasure)
                                treasure = true;
                            if (current == start && c == wall)
                            {
                                current = null;
                                return WallType.Ascend;
                            }
                            if (current == end && c == wall)
                            {
                                current = null;
                                return WallType.Descend;
                            }
                            if (c == wall)
                                return WallType.SolidWall;
                            
                            return WallType.Open;
                        };
                    var north = getWallType(original[x, y - 1]);
                    var south = getWallType(original[x, y + 1]);
                    var west = getWallType(original[x - 1, y]);
                    var east = getWallType(original[x + 1, y]);
                    var location = new Location(west, east, north, south);
                    if(treasure)
                    location.Treasure = rnd.Next(11);
                    result[(x - 1) / 2, (y - 1) / 2] = location;
                }
            }
            return result;
        }
        const char wall = '#';
        const char start = 's';
        const char open = ' ';
        const char end = 'e';
        const char treasure = 't';

        char[,] originalTranslation(int mazeWidth, int mazeHeight, int startX = 0, int startY = 0)
        {
            Debug.Assert(startX >= 0 && startX < mazeWidth * 2 + 1);
            Debug.Assert(startY >= 0 && startY < mazeHeight * 2 + 1);

            // max number of horizontal/vertical walkable tiles



            // var rnd = new Random(2);
            var width = 2 * mazeWidth + 1;
            var height = 2 * mazeHeight + 1;
            var maze = new char[width, height];

            for (var x = 0; x < height; x++)
            {
                for (var y = 0; y < width; y++)
                {
                    maze[x, y] = wall;
                }
            }

            var x_pos = startX * 2 + 1;
            var y_pos = startY * 2 + 1;
            maze[x_pos, y_pos] = start;
            var moves = new Stack<int>();
            var firstPop = true;
            moves.Push(y_pos + (x_pos * width));
            var placedTreasure = false;
            while (moves.Count > 0)
            {


                var possible_directions = string.Empty;
                if (x_pos + 2 < height - 1 && maze[x_pos + 2, y_pos] == wall)
                {
                    possible_directions += "S";
                }

                if (x_pos - 2 >= 0 && maze[x_pos - 2, y_pos] == wall && x_pos - 2 != height - 1)
                {
                    possible_directions += "N";
                }

                if (y_pos - 2 >= 0 && maze[x_pos, y_pos - 2] == wall && y_pos - 2 != width - 1)
                {
                    possible_directions += "W";
                }

                if (y_pos + 2 <= width - 1 && maze[x_pos, y_pos + 2] == wall)
                {
                    possible_directions += "E";
                }

                if (possible_directions.Length > 0)
                {
                    var move = rnd.Next(0, possible_directions.Length);

                    switch (possible_directions[move].ToString())
                    {
                        case "N": maze[x_pos - 2, y_pos] = open;
                            maze[x_pos - 1, y_pos] = open;
                            x_pos -= 2;
                            break;
                        case "S": maze[x_pos + 2, y_pos] = open;
                            maze[x_pos + 1, y_pos] = open;
                            x_pos += 2;
                            break;
                        case "W": maze[x_pos, y_pos - 2] = open;
                            maze[x_pos, y_pos - 1] = open;
                            y_pos -= 2;
                            break;
                        case "E": maze[x_pos, y_pos + 2] = open;
                            maze[x_pos, y_pos + 1] = open;
                            y_pos += 2;
                            break;
                    }
                    moves.Push(y_pos + (x_pos * width));
                }
                else
                {
                    if (firstPop)
                    {
                        firstPop = false;
                        maze[x_pos, y_pos] = end;

                    }
                    else if (!placedTreasure && maze[x_pos,y_pos]==open)
                    {
                        maze[x_pos, y_pos] = treasure;
                        placedTreasure = true;
                    }
                    var back = moves.Pop();
                    decimal stackX = back / width;
                    x_pos = (int)Math.Floor(stackX);
                    y_pos = back % width;
                }
            }
            return maze;
        }
    }
}
